#include "stack_queue.h"
using namespace std;
map<char,int>icp;
map<int,int> isp;
void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}
void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}
/*
*/

listNode::listNode(int nodeData, listNode *succ)
{
    data=nodeData;
    next=succ;
}

MyStack::MyStack()
{
    topNode=new listNode;//初始化一个空栈，只存在一个空节点
    stackSize=0;//栈内元素个数初始化为0（空栈）
}



bool MyStack::push(const int &elem)
{
    if(stackSize==0)//判断是否为空栈
    {
        topNode->data=elem;//若是空栈，则只对此节点赋值
        stackSize++;
        return true;
    }
    listNode* temp;
    temp=new listNode;
    temp->next=topNode;//分配一块节点空间，存入压栈的元素
    temp->data=elem;//将新节点连入链表头
    topNode=temp;//更新栈顶指针
    temp=NULL;
    stackSize++;
    return true;
}

bool MyStack::pop(int &item)
{
    if(topNode->next==NULL)//判断此栈是否仅有一个节点
    {
        if(stackSize==0)//若栈为空栈，则返回false(无法弹出栈顶元素)
        {
            return false;
        }
        else//否则，将栈内元素数置为0，表明其为空栈，可以不操作其中数值(若栈仅有一个节点，栈内元素数只可能为0或1)
        {
            item=topNode->data;
            stackSize--;
            return true;
        }
    }
    listNode* temp;
    temp=new listNode;
    temp->next=topNode;//创建新节点(此处也可仅设置一个指针)，使其指针指向栈顶节点(相当于锚定了栈顶节点空间)
    topNode=topNode->next;//更新栈顶指针
    item=temp->next->data;//获取原栈顶元素
    delete temp->next;
    delete temp;//释放原栈顶节点和新创建的临时节点
    stackSize--;//栈内元素数减1
    return true;
}

bool MyStack::pop()//整体流程同上函数，唯一区别是不需要获取栈顶元素值
{
    if(topNode->next==NULL)
    {
        if(stackSize==0)
        {
            return false;
        }
        else
        {
            topNode->data=-1;
            stackSize--;
            return true;
        }
    }
    listNode* temp;
    temp=new listNode;
    temp->next=topNode;
    topNode=topNode->next;
    delete temp->next;
    delete temp;
    stackSize--;
    return true;
}

bool MyStack::getTop(int &item)
{
    if(stackSize==0)//若空栈，则无法获取栈顶元素
    {
        return false;
    }
    item=topNode->data;
    return true;
}
MyStack::~MyStack()
{
    int temp;
    while(pop(temp))//不断执行弹栈操作直至剩下一个节点
    {
    }
    delete topNode;//释放最后一个节点
}
MyQueue::MyQueue(const int&val) {
    queue = new int[val];//动态申请数组
    capacity = val;
    front = rear = 0;//初始化节点
    cur_num_elem=0;
}
MyQueue::~MyQueue() {
    delete [] queue;
}

bool MyQueue::enQueue(const int&val) {
    if (( rear+ 1) % capacity ==front ) { return false; }//满的话不能进队列
    queue[rear] = val; rear = (rear + 1) % capacity;//进队列并更新尾结点
    return true;
}

bool MyQueue::deQueue(int&val) {
    if (rear  == front) { return false; }//空的话无法出队列
    val = queue[front];
    front = (front + 1) % capacity;//出队列并更新头结点
    return true;
}

bool MyQueue::getFront(int&val) {
    if (rear == front) { return false; }//空的话false
    val = queue[front]; return true;//返回队头数值
}

bool MyQueue::isFull()
{
    if(cur_num_elem==capacity)
    {
        return true;
    }
    return false;
}
bool checkExpression(const string&exp)
{
    int left=0;
    bool flag=true;
    for(int i=0;i<exp.size();i++)
    {
        int temp=exp[i];
        if(temp>=48&&temp<=57)
        {
            flag=false;
            continue;
        }
        else if(exp[i]=='+'||exp[i]=='-'||exp[i]=='*'||exp[i]=='/'||exp[i]==')')
        {
            if(flag)
            {
                return false;
            }
            if(exp[i]=='/')
            {
                if(exp[i+1]==48)
                {
                    return false;
                }
            }
            if(exp[i]==')')
            {
                left--;
                if(left<0)
                {
                    return false;
                }
                flag=false;
            }
            else
            {
                flag=true;
            }
        }
        else if(exp[i]=='(')
        {
            left++;
            flag=true;
        }
        else
        {
            return false;
        }
    }
    if(left!=0||flag)
    {
        return false;
    }
    return true;
}
bool postfixExpression(const string&exp, string&exp0)
{
    if(!checkExpression(exp))
    {
        exp0="Expression is wrong!";
        return false;
    }
    icp['+']=2;
    icp['-']=2;
    icp['*']=4;
    icp['/']=4;
    icp['(']=8;
    icp[')']=1;
    icp['#']=0;
    isp[0]=0;
    isp[2]=3;
    isp[4]=5;
    isp[8]=1;
    isp[1]=8;
    MyStack charStack;
    string result="#";
    int a;
    a='#';
    charStack.push(a);
    for(int i=0;i<exp.size();i++)
    {
        int temp;
        temp=exp[i];
        if(temp>=48&&temp<=57)
        {
            result=result+exp[i];
        }
        else
        {
            int b;
            char top_op;
            char now_op=exp[i];
            while(1)
            {
                charStack.getTop(b);
                top_op=b;
                if(icp[now_op]>isp[icp[top_op]])
                {
                    int c=now_op;
                    charStack.push(c);
                    break;
                }
                else if(icp[now_op]==isp[icp[top_op]])
                {
                    charStack.pop();
                    break;
                }
                else
                {
                    result=result+top_op;
                    charStack.pop();
                }
            }
        }
    }
    int n;
    while(1)
    {
        charStack.pop(n);
        char op=n;
        if(op=='#')
        {
            break;
        }
        else
        {
            result=result+op;
        }
    }
    result.erase(0,1);
    exp0=result;
    return true;
}

bool expressionVal(const string &exp, int &val)
{
    string result;
    if(!postfixExpression(exp,result))
    {
        val=0;
        return false;
    }
    MyStack numStack;
    for(int i=0;i<result.size();i++)
    {
        if(result[i]>=48&&result[i]<=57)
        {
            numStack.push(result[i]-48);
        }
        else
        {
            int num1,num2;
            numStack.pop(num2);
            numStack.pop(num1);
            char op=result[i];
            switch(op)
            {
                case '+':
                    numStack.push(num1+num2);
                    break;
                case '-':
                    numStack.push(num1-num2);
                    break;
                case '*':
                    numStack.push(num1*num2);
                    break;
                case '/':
                    numStack.push(num1/num2);
                    break;
            }
        }
    }
    numStack.getTop(val);
    return true;
}

void yanghui(const int &n)
{
    int first=1;
    MyQueue tri(n+5);
    tri.enQueue(0);
    tri.enQueue(first);
    tri.enQueue(0);
    int count=0;
    int head;
    int out;
    while(count<n)
    {
        tri.deQueue(out);
        tri.getFront(head);
        cout<<head+out;
        tri.enQueue(head+out);
        if(head==0)
        {
            tri.enQueue(0);
            cout<<endl;
            count++;
        }
        else
        {
            cout<<",";
        }
    }
}

